package solution1.demo.demo13;

import java.util.Arrays;

public class Solution {

////    //快速排序
////    public void quickSort(int[] arr) {
////        quick(arr, 0, arr.length - 1);
////    }
////
////    private void quick(int[] arr, int left, int right) {
////        if(left >= right) {
////            return;
////        }
////        //寻找基准
////        int point = fundPoint(arr, left, right);
////        quick(arr, left, point - 1);
////        quick(arr, point + 1, right);
////    }
////
////    private int fundPoint(int[] arr, int left, int right) {
////        int key = arr[left];
////        while(left < right) {
////            while(left < right && arr[right] >= key) {
////                right--;
////            }
////            arr[left] = arr[right];
////            while(left < right && arr[left] <= key) {
////                left++;
////            }
////            arr[right] = arr[left];
////        }
////        arr[left] = key;
////        return left;
////    }
//
//    //归并排序
//    public void mergeSort(int[] arr) {
//        mergeFun(arr, 0, arr.length - 1);
//    }
//
//    private void mergeFun(int[] arr, int left, int right) {
//        if(left >= right) {
//            return;
//        }
//        int mid = (left + right) / 2;
//        mergeFun(arr, left, mid);
//        mergeFun(arr, mid + 1, right);
//        //合并
//        merge(arr, left, right, mid);
//    }
//
//    private void merge(int[] arr, int left, int right, int mid) {
//        int[] tmpArr = new int[right - left + 1];
//        int index = 0;
//        int s1 = left;
//        int s2 = mid + 1;
//        while(s1 <= mid && s2 <= right) {
//            if(arr[s1] < arr[s2]) {
//                tmpArr[index++] = arr[s1++];
//            } else {
//                tmpArr[index++] = arr[s2++];
//            }
//        }
//        while(s1 <= mid) {
//            tmpArr[index++] = arr[s1++];
//        }
//        while(s2 <= right) {
//            tmpArr[index++] = arr[s2++];
//        }
//        for(int i = 0; i < index; i++) {
//            arr[i + left] = tmpArr[i];
//        }
//    }
//
//    //堆排序
//    public void heapSort(int[] arr) {
//        //创建大根堆
//        createHeap(arr);
//        //每次与最后一个待排序的元素交换
//        for(int i = arr.length - 1; i > 0; i--) {
//            swap(arr, 0, i);
//            adjustDown(arr, 0, i);
//        }
//    }
//
//    private void createHeap(int[] arr) {
//        //从最后一颗子树开始向下调整
//        int len = arr.length;
//        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--) {
//            adjustDown(arr, parent, len);
//        }
//    }
//
//    private void adjustDown(int[] arr, int parent, int len) {
//        int child = parent * 2 + 1;
//        while(child < len) {
//            if(child + 1 < len && arr[child + 1] > arr[child]) {
//                child++;
//            }
//            if(arr[child] > arr[parent]) {
//                //交换
//                swap(arr, child, parent);
//                //继续调整
//                parent = child;
//                child = child * 2 + 1;
//            } else {
//                break;
//            }
//        }
//    }
//
//    private void swap(int[] arr, int child, int parent) {
//        int tmp = arr[child];
//        arr[child] = arr[parent];
//        arr[parent] = tmp;
//    }
//
//    public void mergeSort(int[] arr) {
//        mergeFun(arr, 0, arr.length - 1);
//    }
//
//    private void mergeFun(int[] arr, int left, int right) {
//        if(left >= right) {
//            return;
//        }
//        int mid = (left + right) / 2;
//        mergeFun(arr, left, mid);
//        mergeFun(arr, mid + 1, right);
//        merge(arr, left, right, mid);
//    }
//
//    private void merge(int[] arr, int left, int right, int mid) {
//        int[] tmpArr = new int[right - left + 1];
//        int index = 0;
//        int s1 = left;
//        int s2 = mid + 1;
//        while(s1 <= mid && s2 <= right) {
//            if(arr[s1] < arr[s2]) {
//                tmpArr[index++] = arr[s1++];
//            } else {
//                tmpArr[index++] = arr[s2++];
//            }
//        }
//        while(s1 <= mid) {
//            tmpArr[index++] = arr[s1++];
//        }
//        while(s2 <= right) {
//            tmpArr[index++] = arr[s2++];
//        }
//        for(int i = 0; i < index; i++) {
//            arr[i + left] = tmpArr[i];
//        }
//    }


    //快排
    public void quickSort(int[] arr) {
        quickFun(arr, 0, arr.length - 1);
    }

    private void quickFun(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int point = fundPoint(arr, left, right);
        quickFun(arr, left, point - 1);
        quickFun(arr, point + 1, right);
    }

    private int fundPoint(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) {
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
    
    //归并排序
    public void mergeSort(int[] arr) {
        mergeFun(arr, 0, arr.length - 1);
    }

    private void mergeFun(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeFun(arr, left, mid);
        mergeFun(arr, mid + 1, right);
        merge(arr, left, right, mid);
    }

    private void merge(int[] arr, int left, int right, int mid) {
        int[] tmpArr = new int[right - left + 1];
        int index = 0;
        int s1 = left;
        int s2 = mid + 1;
        while(s1 <= mid && s2 <= right) {
            if(arr[s1] < arr[s2]) {
                tmpArr[index++] = arr[s1++];
            } else {
                tmpArr[index++] = arr[s2++];
            }
        }
        while(s1 <= mid) {
            tmpArr[index++] = arr[s1++];
        }
        while(s2 <= right) {
            tmpArr[index++] = arr[s2++];
        }
        for(int i = 0; i < index; i++) {
            arr[i + left] = tmpArr[i];
        }

    }



}


class Main {
    public static void main(String[] args) {
        int[] arr = {3,1,2,5};
        Solution solution = new Solution();
        solution.mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}


